<?php
/**
 * User: LRZ
 * Date: 2020/1/16
 * Time: 14:31
 */

/**
 *  849.到最近的人的最大距离
 *
 *  标签：数组
 *
 *  在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
 *  至少有一个空座位，且至少有一人坐在座位上。
 *  亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
 *  返回他到离他最近的人的最大距离。
 *
 *  示例 1：
 *      输入：[1,0,0,0,1,0,1]
 *      输出：2
 *      解释：
 *          如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
 *          如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
 *          因此，他到离他最近的人的最大距离是 2 。
 *
 *  示例 2：
 *      输入：[1,0,0,0]
 *      输出：3
 *      解释：
 *          如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
 *          这是可能的最大距离，所以答案是 3 。
 *
 *  提示：
 *      1 <= seats.length <= 20000
 *      seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/maximize-distance-to-closest-person
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$seats = [1, 0, 0, 0, 1, 0, 1];
$res   = maxDistToClosest($seats);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function maxDistToClosest($seats)
{
    $e   = 0;
    $max = 0;
    foreach ($seats as $k => $v) {
        if ($e === $k) {
            $max = $e;
        } else {
            $max = max($max, ($e + $e % 2) / 2);
        }
        if ($v === 1) {
            $e = 0;
        } else {
            $e++;
        }
    }
    return max($max, $e);
}